 #
# @lc app=leetcode.cn id=312 lang=python3
#
# [312] 戳气球
#

# @lc code=start
class Solution:
    def maxCoins(self, nums: List[int]) -> int:
        nums.insert(0,1)
        nums.insert(len(nums), 1)

        m = len(nums)
        dp = [[0]*m for _ in range(m)]

        for n in range(2, m): # 区间长度的
            print(f'n={n}')
            for i in range(0, m-n):
                res = 0
                j = i+n
                for k in range(i+1, j):
                    print(f'i={i} k={k} j={j}', end=' ')
                    res = dp[i][k]+nums[i]*nums[k]*nums[j]+dp[k][j]
                    print(f'{res}={dp[i][k]}+{nums[i]*nums[k]*nums[j]}+{dp[k][j]}', end=' ')
                    dp[i][j] = max(res, dp[i][j])
                    print(f'dp[{i}][{j}]={dp[i][j]}')

        return dp[0][m-1]
# @lc code=end

